home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3859 < prev    next >
Encoding:
Text File  |  1996-08-05  |  3.1 KB  |  102 lines
  1. Path: else.net!tor250!org!gryn!fknights!andrew.frank
  2. From: Andrew.Frank@fknights.gryn.org (Andrew Frank)
  3. Date: 29 Jan 96 16:50:51 
  4. Newsgroups: comp.lang.c
  5. Subject: Re: Finding a prime number
  6. Message-ID: <7c8_9601301722@tor250.org>
  7. References: <4e875s$nqk@reader2.ix.netcom.com>
  8. X-FTN-To: advtr@ix.netcom.com
  9. Organization:  fks Online! * Ontario, Canada * (905)820-7273 * 
  10.  
  11. As advtr@ix.netcom.com had made knowen to All, on 25 Jan 96  10:21:32, I
  12. quote.
  13.  ad> From: advtr@ix.netcom.com(Advance Trading)
  14.  ad> Subject: Finding a prime number
  15.  ad> Organization: Netcom
  16.  
  17.  ad> I need to write a function that will find wether or not a number is
  18.  ad> prime.  I can come close but I get numbers that are not prime with the
  19.  ad> prime numbers.
  20.  
  21.  I recently wrote a program to do this.  It will take about 10
  22.  seconds to process a little at the start, but will then quickly tell
  23.  if any number between 4 and 4.2 billion is prime.  Here is the
  24.  source code.
  25.  
  26.  ---------------- Code Start __________________
  27. /* Filename: PRIMETST.C */
  28. /* Tests to see if a given number is prime. */
  29. /* Requires a few seconds at startup to determine the low primes */
  30. #include <stdio.h>
  31. #include <stdlib.h>
  32.  
  33. main()
  34. {
  35.      unsigned long int I;
  36.      unsigned int J;
  37.      unsigned int P = 1;
  38.      int PRIME = 1;
  39.      unsigned int STACK[6670];
  40.  
  41.      puts("Generating Primes...");
  42.  
  43.      /* Is currently generating all prime numbers below 65535, uses
  44.      these to test higher numbers for primeness. */
  45.  
  46.      STACK[0] = 2;
  47.      for (I = 3; I < 65535; I += 2)
  48.           {       for (J = 1; (long int)STACK[J] * (long int)STACK[J] <= I;
  49. J++)
  50.                     {  if (!(I % STACK[J]))
  51.                          {       PRIME = 0;
  52.                               break;
  53.                          }
  54.                     }
  55.                if (PRIME)
  56.                     {       P++;
  57.                          STACK[P] = I;
  58.                     }
  59.                PRIME = 1;
  60.           }
  61.      puts("Done.");
  62.  
  63.      while(1)
  64.      {
  65.           puts("Enter a number to test (under 4.2 billion), 0-3 quits");
  66.           scanf(" %ul", &I);
  67.           if (I < 4)
  68.           {       exit(1);}
  69.  
  70.           /* Tests inputted number against previous primes up until
  71.           the square root of the number your checking */
  72.  
  73.           for (J = 0; (long int)STACK[J] * (long int)STACK[J] <= I; J++)
  74.           {
  75.                if (!(I % STACK[J]) && !(I / STACK[J] == 1))
  76.                {       PRIME = 0;
  77.                     break;
  78.                }
  79.           }
  80.  
  81.           if (PRIME)
  82.                puts("Prime!");
  83.           if (!(PRIME))
  84.                puts("Not Prime.");
  85.  
  86.           PRIME = 1;
  87.      }
  88.      return 0;
  89. }
  90. -------------------- End Program Listing ----------------------
  91.  
  92. There.  Just cut between the lines, and compile it.  It's most
  93. efficient if you have many numbers to test.  There is a simpler and
  94. faster way if you only have one number to test (although this is
  95. reasonably simply for you because all you have to do now is cut and
  96. compile).
  97.  
  98. ... Newspaper Ad:  Dog for sale: eats anything and is fond of children.
  99. --
  100. | Fidonet:  Andrew Frank 1:259/423
  101. | Internet: Andrew.Frank@fknights.gryn.org
  102.